<head>
    <meta charset="UTF-8">
<title>算法训练 最短路</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div class="sec_header">
问题描述</div>
<div class="sec_cont">
	<p>给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。</p>
</div>
<div class="sec_header">
输入格式</div>
<div class="sec_cont">
	<p>第一行两个整数n, m。</p>
	<p>接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。</p>
</div>
<div class="sec_header">
输出格式</div>
<div class="sec_cont">
	共n-1行，第i行表示1号点到i+1号点的最短路。
</div>
<div class="sec_header">
样例输入</div>
<div class="sec_text">
3 3<br />
1 2 -1<br />
2 3 -1<br />
3 1 2	

</div>
<div class="sec_header">
样例输出</div>
<div class="sec_text">
-1<br />
-2

	</div>
<div class="sec_header">
数据规模与约定</div>
<div class="sec_cont">
<p>对于10%的数据，n = 2，m = 2。</p>
<p>对于30%的数据，n &lt;= 5，m &lt;= 10。</p>
<p>对于100%的数据，1 &lt;= n &lt;= 20000，1 &lt;= m &lt;= 200000，-10000 &lt;= l &lt;= 10000，保证从任意顶点都能到达其他所有顶点。</p>
</div>
